﻿#include "IntegerAddMinusMultiDivide.h"
#include "TestingUtil.h"

int IntegerAddMinusMultiDivide::negNum(int num)
{
	return  add(~num , 1);
}

int IntegerAddMinusMultiDivide::add(int a, int b)
{
	while(b!=0)
	{
		const int sum0 = a ^ b;
		const int sum1 = (a & b) << 1;

		a = sum0;
		b = sum1;
	}
	return a;
}

int IntegerAddMinusMultiDivide::minus(int a, int b)
{
	return add(a, negNum(b));
}

int IntegerAddMinusMultiDivide::multi(int a, int b)
{
	if (a == 0 || b == 0)
		return 0;

	int absA = a < 0 ? negNum(a) : a;
	int absB = b < 0 ? negNum(b) : b;

	int multiResult = 0;
	while(absB>0)
	{
		if(absB & 1)
			multiResult = add(multiResult, absA);

		absB >>= 1;
		absA <<= 1;
	}

	const bool isNegative = (a < 0) != (b < 0);
	return isNegative ? negNum(multiResult) : multiResult;
}

int IntegerAddMinusMultiDivide::div(int a, int b)
{
	if (a == INT_MIN && b == INT_MIN)
		return 1;
	else if (b == INT_MIN)
		return 0;
	else if(a==INT_MIN)
	{
		if (b == -1)
			return INT_MAX;
		else
		{
			const int resultMain = div(add(a, 1), b);
			const int resultLeft = div(minus(a, multi(resultMain, b)), b);
			const int result= add(resultMain, resultLeft);
			return result;
		}
	}
	else
	{
		int absA = a < 0 ? negNum(a) : a;
		int absB = b < 0 ? negNum(b) : b;

		int result = 0;
		for (int i = 30; i >= 0; i = minus(i, 1))
		{
			if ((absA >> i) >= absB)
			{
				result |= (1 << i);
				absA = minus(absA, absB << i);
			}
		}
		const bool isNegative = (a < 0) != (b < 0);
		return isNegative ? negNum(result) : result;
	}
}

#ifdef DEV_TEST
#include <gtest/gtest.h>
TEST(IntegerAddMinusMultiDivideTest, negNum)
{
	std::vector<int> numsToNegtive;
	numsToNegtive.emplace_back(0);
	numsToNegtive.emplace_back(INT_MIN);
	numsToNegtive.emplace_back(INT_MAX);

	for (int i = 0; i < 1000; ++i)
		numsToNegtive.emplace_back(TestingUtil::randInt());

	for (auto& num : numsToNegtive)
		EXPECT_EQ(IntegerAddMinusMultiDivide::negNum(num), -num);
}

TEST(IntegerAddMinusMultiDivideTest, add)
{
	auto nums= TestingUtil::randSizedInts(10000);

	for(int i=0;i<nums.size()-1;++i)
		EXPECT_EQ(IntegerAddMinusMultiDivide::add(nums[i], nums[i + 1]), nums[i] + nums[i + 1]);
}

TEST(IntegerAddMinusMultiDivideTest,minus)
{
	auto nums = TestingUtil::randSizedInts(10000);

	for (int i = 0; i < nums.size() - 1; ++i)
		EXPECT_EQ(IntegerAddMinusMultiDivide::minus(nums[i], nums[i + 1]), nums[i] - nums[i + 1]);
}

TEST(IntegerAddMinusMultiDivideTest, multi)
{
	//std::cout << INT_MIN * 2 << std::endl;//0
	//std::cout << INT_MIN * -2 << std::endl;//0
	//std::cout << INT_MIN * 1 << std::endl;//INT_MIN
	//std::cout << INT_MIN * -1 << std::endl;//INT_MIN
	//std::cout << INT_MAX * 2 << std::endl;//-2
	//std::cout << INT_MAX * -2 << std::endl;//2
	//std::cout << INT_MAX * 1 << std::endl;//INT_MAX
	//std::cout << INT_MAX * -1 << std::endl;//-INT_MAX

	std::vector<int> nums{ 0,0,1,1 };
	for (int i = 0; i < 1000; ++i)
		nums.emplace_back(TestingUtil::randInt());

	for (int i = 0; i < nums.size() - 1; ++i)
		for (int j = i + 1; j < nums.size(); ++j)
			ASSERT_EQ(IntegerAddMinusMultiDivide::multi(nums[i], nums[j]), nums[i] * nums[j])
					<< "nums[i]:" << nums[i] << " nums[j]:" << nums[j];
}

TEST(IntegerAddMinusMultiDivideTest, div)
{
	std::vector<int> nums{ 1,0,INT_MIN,INT_MAX };
	for (int i = 0; i < 1000; ++i)
		nums.emplace_back(TestingUtil::randInt());

	for (int i = 0; i < nums.size() - 1; ++i)
		for (int j = i + 1; j < nums.size(); ++j)
		{
			if (nums[j] == 0)
				continue;
			ASSERT_EQ(IntegerAddMinusMultiDivide::div(nums[i], nums[j]), nums[i] / nums[j])
				<< "nums[i]:" << nums[i] << " nums[j]:" << nums[j];
		}
}
#endif

